\chapter{Advanced Approach}
\label{chap:Advanced Approach}

\section{Ants Cooperation}
\label{Ants Cooperation}
\subsection{Introduction}
\label{Introduction}
 In the third chapter, I discussed the parent class of the agents. In this chapter, I will clarify the extensions of the parent class to different children classes. Each of the children classes has unique properties, different state machines and priority lists. Different agents can understand the differences between each others and know the capabilities of each others. Moreover, I will discuss the role of each child class in both the types of teamwork.
\subsection{Dependent Teamwork}
\label{Dependent Teamwork}
 The dependent teamwork objective is allocating resources and acquiring them. There are many strategies behind this mission such as distribution of ants upon different resources, or finding shortest paths. Roughly, discovery ants should explore the whole map and inform the alarm ant. The alarm ant creates paths and strategies and informs worker ants. The worker ants follow the orders and perform the mission. The dependency here is that the workers depend on both discovery and alarm ants in order to work. The alarm ant depends on discovery ants in order to issue jobs for the workers. Discovery ants depend on the alarm ant in order to go outside the nest and explore the surrounding. Therefore, there is a dependency cycle where the whole community jobs depend on each others. The following figure shows the dependency cycle briefly. 

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.9\textwidth]{cycle.png} 
\caption{Dependency Cycle}
\label{Dependency Cycle}
\end{center}
\end{figure}

\subsection{Independent Teamwork}
\label{Independent Teamwork}
 The independent teamwork objective is to defend the nest. The alarm ant is responsible for verifying any invasion. It acts as a radar that surrounds the nest with a certain sensory circle. Once an attack is being verified, the alarm ant leaves a message in the nest and goes outside to call other ants nearby to cancel their missions and defend their nest. Roughly, the alarm ant detects the enemies and tries to call as much as possible ants. The discovery ants distribute themselves around the nest and try to stun as much as possible enemies. The worker ants attack the enemies once they are informed regardless to their state and given jobs. They kill enemies that attack the nest before the stunned enemies. Unlike the dependent teamwork, none of the ants depend on the other, once any ant verifies an attack, it performs it's defending job independently. 



\section{Discovery Ant}
\label{Discovery Ant}

\subsection{Tasks Implementation}
\label{Tasks Implementation}
The colony has four discovery ants. They have two tasks. The first task (dependent task) is to explore the map. In order to have an efficient map exploration, some mandatory parameters must be considered. These parameters are the following: area of the whole map, number of cells broken from the whole map, number of agents available and an algorithm that can distribute jobs on agents based on total time taken in jobs \cite{twentytwo}. The map is distributed into a 2d array relative to the 2d coordinate system (x,z). Each cell in the 2d array corresponds to a certain area that doesn't intersect other areas. The whole map is broken into thirty six smaller cells. Discovery ants pick cells from the 2d array and go explore them through reaching their centers. As for algorithm of work distribution, it is explained in the strategy section of the discovery ant. 
\\

Each ant picks a cell and can neither pick a cell picked by someone else nor pick two cells at a time. In some special cases, they can pick others cells. Example, a discovery ant X picks a cell Y and while exploring it, an enemy attacked the nest. Ant X then canceled its mission and done another defending mission. It might be that when defending is finished, it picks another cell Z leaving this cell Y for other ants to pick. Once a cell is picked the discovery ant tries to explore it, it is possible that there is a dead lock that prevents the discovery ant from reaching this area. If this is the case, the whole area is regarded as non reachable or an obstacle.  After finishing the exploring process, ants verify the whole map, then data is given to the alarm ant at once. Discovery ants then stay in the nest until they take another mission for discovering a map or defending the nest. The dependency in this task is, it is done upon request from the alarm ant, whether initially at the beginning of the simulation or later when the environment has a change after discovering the map.
\\

 The other task is the defending task (independent task). In this task the discovery ants learn about the attack, either from the message left by the alarm ant in the nest, or while doing a discovery mission by hearing the alarm ant recalling. Once an attack is verified, the discovery ants distribute themselves around the corners of the nest. Picking corners has no selection criteria except that they just pick corners not picked by others. After that the ants keep stunning enemy ants trying to pass to their nest. However, there are some areas between them not covered, thus not all of the enemy ants are stunned. The stunning radius length is equal to half the distance between the ant and the center of the nest. Regardless of other ants' jobs, they keep stunning any enemy ant that comes in their radius until the alarm is set off and no more are enemies nearby the nest. Such a system has limitations because some enemies will be able to bypass them. However, discovery ants play a successful role of distracting enemy forces by reducing the number of ants attacking the nest. The following figure shows how they work. 

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{discovery_defence.png} 
\caption{Discovery ants doing their defensive job}
\label{Discovery ants doing their defensive job}
\end{center}
\end{figure}
\subsection{State Diagram}
\label{State Diagram}
The following figure represents the state diagram of a discovery ant.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.7\textwidth]{state_diagram_11.png} 
\caption{State Machine of a Discovery Ant}
\label{State Machine of a Discovery Ant}
\end{center}
\end{figure}

\subsection{Priority System}
\label{Priority System}
The following figure represents the priority list of a discovery ant. 
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.7\textwidth]{priority_discovery.png} 
\caption{Priority List of a Discovery Ant}
\label{Priority List of a Discovery Ant}
\end{center}
\end{figure}

Priority list has one component (protection). As for the protection component there are three parameters, house alarm, ants messages and information about the enemy (explained earlier in chapter 3). Both house alarm and ants messages (alarm ant recalling) have the same priority. Once the discovery ant is called by one of them it directly transfers to defensive job. As for enemy information discovery ants do not care except for enemies are present or not and discovery ants affect this parameter by sending info about stunned enemies. As for mandatory components for protection, there is only the parameter strategies.
\\

 As for strategies, there are two types, strategies regarding defending and strategies regarding map discovering. As for strategies regarding defending discovery ants distribute themselves on four corners by a distance twice their stunning radius from the nest. It is true that the more the discovery ant far from the nest the earlier it stops the enemies from approaching. However, it will have less probability of stunning enemies since the stunning radius is the same. Strategies regarding map discovering are concerned with time. The exploring job is not distributed equally between the ants in terms of quantity. Once an ant finishes its job it is assigned a new one, so if an ant finishes its jobs fast, it will get more jobs than others. Even if it means an unfair job distribution among the agents, it is still better in saving time. Imagine there are four jobs a, b, c, and d, as well as two ants x and y. let's assume jobs a, b and c take 2 minutes each, while job d takes 7 minutes. If you distribute the jobs equally, then x will take jobs a and b and finish them in 4 minutes, while y will take jobs c and d and finish them in 9 minutes. The whole job took 9 minutes to be finished. If x takes jobs a, b and c, while y takes job d, then x will finish in 6 minutes and y will finish in 7 minutes. The whole job took 7 minutes to be finished. That is the strategy used by discovery ants to finish discovering the map as fast as possible.  
\section{Alarm Ant}
\label{Alarm Ant}
\subsection{Tasks Implementation}
\label{Tasks Implementation}
The colony has one alarm ant. It has two tasks. The first task (dependent task) is to plan for the jobs of the colony. Any social system requires some coordination of action. Individuals need to take certain roles, and high-level goals need to be solved by occasionally non obvious, low-lever cooperative action \cite{fifteen}. The alarm ant giving out tasks in a central location basically corresponds to a so called "Blackboard Architecture". A blackboard system is an artificial intelligence application, where a common knowledge base, the alarm ant (blackboard), is iteratively updated by different ants (knowledge sources). These updates help in solving the main problem. Example, alarm ant wants to create a path for worker ants, but lacks different information on different paths. As more discovery ants update more portions of the map, the problem is on its way to solving. Alarm ant doesn't stop at just issuing jobs, but also perform calculations and creates shortest paths of worker ants. Dijkstra algorithm is used in order to resolve the shortest path.
\subsubsection{Dijkstra's Algorithm}
\label{Dijkstra's Algorithm}
Dijkstra's algorithm solves the problem of finding the shortest path from a point in a graph (the source) to a destination. The algorithm finds the shortest path between every point and all other points. It can also be used to search for only a certain point and once found, searching is terminated. In our case, we will use it to find all shortest paths to all points from a source. The idea of the algorithm is to begin with a starting point, and find the distances to all points connected to the starting point and recording them with their distances. Pick the one nearest to the starting point and again research with the same way and then check other points. After researching do the same with points connected to the points connected to the starting point and so on until you calculate the whole points. While calculating there will be different ways for the same points with different distances, only the way with the minimum distance is being recorded.
\\

In our case we mainly do the same by having a starting point which is the nearest to the nest. Each point is connected with eight different points which are top, bottom, left, right and the four corners. The distances to top, bottom, left and right are 1 unit, while to the corners are $\sqrt{2}$ unit. We start by the starting point and update the distances of the eight points. Then we save at each point it's shortest path from the starting point based on the distance. We then perform the same till we finish the whole map. Obstacles points are regarded as points not connected and not calculated in our calculations. Since each step in Dijkstra's algorithm requires a number of operations proportional to $|N|$, and the steps are iterated $|N-1|$ times, the worst case computation is $O(|N|^2)$ \cite{thirteen}.
\\

On the other hand, the other task is the defending task (independent task). In this task alarm ant has radar set on the nest that detects enemies trying to attack the nest. Once they enter the radar radius, alarm ant starts it's defending task. First, it leaves a message inside the nest to all ants inside, or those who will enter the nest. Second, Alarm ant allocates four corners around the nest and keeps moving between them and keeps calling for nearby ants to come and defend the nest. Last but not least once the defending mission is finished and all enemies are killed alarm ant is responsible for issuing new missions for collecting materials to repair the nest. The following figure shows how alarm ant performs the defending job.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.95\textwidth]{alarm_defence.png} 
\caption{Alarm ant doing its defensive job}
\label{Alarm ant doing its defensive job}
\end{center}
\end{figure}

\subsection{State Diagram}
\label{State Diagram}
The following figure represents the state diagram of an alarm ant.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.7\textwidth]{state_diagram_22.png} 
\caption{State Machine of an Alarm ant}
\label{State Machine of an Alarm ant}
\end{center}
\end{figure}

\subsection{Priority System}
\label{Priority System}
The following figure represents the priority list of an alarm ant. 
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.7\textwidth]{priority_alarm.png} 
\caption{Priority List of an Alarm Ant}
\label{Priority List of an Alarm Ant}
\end{center}
\end{figure}
The alarm ant has no elements in the priority list, however, it affects the parameters of all the elements in the priority lists of other agents. As for protection component, there are three parameters, house alarm, ants' messages and information about the enemy. Both house alarm and ants messages (alarm ant recalling) are caused by the alarm ant. As for the information about the enemy, it is affected by the alarm ant by sending information about the number of enemies detected and their positions. As for Safety component, there are three parameters, house damage, repair materials places and available workers. Alarm ant affects all of them as it calculates the damage caused to the nest and required repairing materials (house damage). It can change the worker ants' jobs from collecting food to materials (available workers). It also allocates shortest paths to building materials for them (repair materials places). As for resources component, alarm ant deals the same way as in safety components. As for mandatory components, there are two components (map update and strategies) . As for map update, alarm ant does nothing except asking discovery ants to re-explore the map, if by any means the map is out of date.
\\

As for strategies, there are many different types of strategies performed by the alarm ant. First, it is the only ant that can affect all items in the priority list. Second, it is the ant responsible for distribution of worker ants on the map. When there are many resources on the map, the alarm ant sends a number of worker ants to the nearest source equal to the maximum required ants to deplete that resource. There are many strategies buried behind this plan. It is efficient, as only the required number of ants are sent, as well as it yields the maximum amount of resource collected \cite{eighteen}. It also supports the nest with some ants to defend it in case of an attack. It makes sure that all ants will return to the nest soon in case of any updates, since they are sent to the nearest source only. Third type of strategy used by alarm ant is choosing the type of required resource, whether it is food or building materials. Whenever the house is damaged it requires exactly the same amount of building materials to avoid wasted time in getting extra materials, could have used that time to get food. Last but not least it plans all paths for all worker ants and all algorithms and strategies used by other types of ants are originally the alarm ant creation.

\section{Worker Ant}
\label{Worker Ant}

\subsection{Tasks Implementation}
\label{Tasks Implementation}
The colony has many worker ants. They have two tasks. The first task (dependent task) is gathering resources. The worker ants are the most dependent ants. To gather a resource they need discovery ants to explore the map first. After that they depend on the alarm ant to create paths for them, build some strategies for them and issue them some orders. After that worker ants follow the paths to the resource and carry it to the nest and so on till all resources are depleted. In case of any sudden change in the environment, for example worker ants went to a resource and found it missing or found an obstacle in their way, they inform the alarm ant which by default informs the discovery ants and again map is updated and paths are created and resources are collected.
\\

The other task (independent task) is killing enemies. Worker ants are informed with the presence of enemies, either by alarm ant recalling or by nest message left by the alarm ant. Once they are informed they perform their task which is killing enemies. They start by enemies that are not stunned and attacking the nest. Once they finish killing them they turn to the stunned enemies and deal with them. They attack as a whole group enemy ants ant by ant and not distribute themselves upon the enemy ants. Once they finish killing them they go back to their original mission unless the alarm ant has another point of view. The following figure shows how worker ants perform the defending job.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.9\textwidth]{worker_defence.png} 
\caption{Worker ants doing their defensive job}
\label{Worker ants doing their defensive job}
\end{center}
\end{figure}
\clearpage  
\subsection{State Diagram}
\label{State Diagram}
The following figure represents the state diagram of a worker ant.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.55\textwidth]{state_diagram_33.png} 
\caption{State Machine of a Worker Ant}
\label{State Machine of a Worker Ant}
\end{center}
\end{figure}

\subsection{Priority System}
\label{Priority System}
The following figure represents the priority list of a worker ant. 
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.7\textwidth]{priority_worker.png} 
\caption{Priority List of a Worker Ant}
\label{Priority List of a Worker Ant}
\end{center}
\end{figure}
Priority list has three components. Worker ants are affected by all priority components. As for protection components, there are three parameters, house alarm, ants' messages and information about the enemy. Both house alarm and ants' messages (alarm ant recalling) are two different ways with equal priorities to make worker ants stop their missions and fallback to defend the nest. As for the information about the enemy, worker ants need to know the number of enemies attacking, as well as their positions and states (stunned or no). As for Safety components there are three parameters, house damage, repair materials places and available workers. Worker ants are affected by all of them. They need to know how much repairing materials are required (house damage), which paths to follow (materials places) and how many ants are sent (available workers). As for other resources component, it is pretty much the same as safety but deals with other resources as food piles.
\\

On the other hand there are mandatory components required to perform these priorities. As for map updates, worker ants need it to be updated and follow different paths for resources. As for strategies worker ants are the dumbest. They don't create strategies, they just follow their master's orders (alarm ant). The only strategy they have is attacking normal enemies then stunned ones.
\section{Enemy Ant}
\label{Enemy Ant}

\subsection{Tasks Implementation}
\label{Tasks Implementation}
Enemy ants have only one task which is target the nest and keep attacking it until it is destroyed. See
 \hyperref[Discovery ants doing their defensive job]{''Figure 4.2''},
\hyperref[Alarm ant doing its defensive job]{''Figure 4.4''}and
 \hyperref[Worker ants doing their defensive job]{''Figure 4.6''}.

\subsection{State Diagram}
\label{State Diagram}
The following figure represents the state diagram of an enemy ant.
\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.8\textwidth]{state_diagram_44.png} 
\caption{State Machine of an Enemy ant}
\label{State Machine of an Enemy ant}
\end{center}
\end{figure}

